Farkas' lemma

Farkas' lemma is a result in mathematics stating that a vector is either in a given convex cone or that there exists a (hyper)plane separating the vector from the cone, but not both. It was originally proved by the Hungarian mathematician Gyula Farkas (1894, 1902). It is used amongst other things in the proof of the Karush–Kuhn–Tucker theorem in nonlinear programming.

Farkas' lemma is an example of a theorem of the alternative; a theorem stating that of two systems, one or the other has a solution, but not both or none.

1 Statement of the lemma
2 Geometric interpretation
3 Further implications
4 References
5 Notes

Statement of the lemma

Let A be an m × n matrix and b an m-dimensional vector. Then, exactly one of the following two statements is true:

There exists an x ∈ Rⁿ such that Ax = b and x ≥ 0.
There exists a y ∈ R^m such that A^Ty ≥ 0 and b^Ty < 0.

Here, the notation x ≥ 0 means that all components of the vector x are nonnegative.

There are a number of slightly different (but equivalent) formulations of the Lemma in the literature. The one given here is due to Gale, Kuhn and Tucker in 1951.

Geometric interpretation

Let a₁, …, a_n ∈ R^m denote the columns of A. In terms of these vectors, Farkas' lemma states that exactly one of the following two statements is true:

There exist non-negative coefficients x₁, …, x_n ∈ R such that b = x₁a₁ + ··· + x_na_n.
There exists a vector y ∈ R^m such that a_i · y ≥ 0 for i = 1, …, n and b · y < 0.

The vectors x₁a₁ + ··· + x_na_n with nonnegative coefficients constitute the convex cone of the set {a₁, …, a_n} so the first statement says that b is in this cone.

The second statement says that there exists a vector y such that the angle of y with the vectors a_i is at most 90° while the angle of y with the vector b is more than 90°. The hyperplane normal to this vector has the vectors a_i on one side and the vector b on the other side. Hence, this hyperplane separates the vectors in the cone of {a₁, …, a_n} and the vector b.

For example, let n,m=2 and a₁ = (1,0)^T and a₂ = (1,1)^T. The convex cone spanned by a₁ and a₂ can be seen as a wedge-shaped slice of the first quadrant in the x-y plane. Now, suppose b = (0,1). Certainly, b is not in the convex cone a₁x₁+a₂x₂. Hence, there must be a separating hyperplane. Let y = (1,−1)^T. We can see that a₁ · y = 1, a₂ · y = 0, and b · y = −1. Hence, the hyperplane with normal y indeed separates the convex cone a₁x₁+a₂x₂ from b.

Farkas' lemma can thus be interpreted geometrically as follows: Given a convex cone and a vector, either the vector is in the cone or there is a hyperplane separating the vector from the cone, but not both.

Further implications

Farkas' lemma can be varied to many further theorems of alternative by simple modifications, such as Gordan's theorem: Either $Ax < 0$ has a solution x, or $A^T y = 0$ has a nonzero solution y with y ≥ 0.

A particularly suggestive and easy-to-remember version is the following: if a set of inequalities has no solution, then a contradiction can be produced from it by linear combination with nonnegative coefficients. In formulas: if $Ax$ ≤ $b$ is unsolvable then $y^T A = 0$ , $y^T b = -1$ , $y$ ≥ $0$ has a solution^[1]. (Note that $y^T A$ is a combination of the left hand sides, $y^T b$ a combination of the right hand side of the inequalities. Since the positive combination produces a zero vector on the left and a −1 on the right, the contradiction is apparent.)

References

Berkovitz, Leonard D. (2001), Convexity and Optimization in $\mathbb{R}^n$ , New York: John Wiley & Sons, ISBN 978-0-471-35281-5 .
Farkas, Gyula (1894), "A Fourier-féle mechanikai elv alkamazásai", Mathematikai és Természettudományi Értesítő 12: 457–472 .
Farkas, Julius (Gyula) (1902), "Über die Theorie der Einfachen Ungleichungen", Journal für die Reine und Angewandte Mathematik 124: 1–27, doi:10.1515/crll.1902.124.1, http://gdz.sub.uni-goettingen.de/en/dms/load/img/?PPN=PPN243919689_0124&DMDID=dmdlog4 .
R. T. Rockafellar: Convex Analysis, Princeton University Press, 1979 (See Page 200).
Gale, Kuhn and Tucker: Linear Programming and the Theory of Games, Chapter XII in Koopmans (ed.): Activity Analysis of Production and Allocation, Wiley (1951) and online. See Lemma 1 on page 318.

Kutateladze S., The Farkas Lemma Revisited [1]

Notes

^ Boyd, Stephen P.; Vandenberghe, Lieven (2004) (pdf). Convex Optimization. Cambridge University Press. ISBN 9780521833783. http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf. Retrieved October 15, 2011.